package com.lun.medium;

public class IntegerBreak {
	
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        
        dp[2] = 1;
        
        for(int i = 3; i <= n; i++) {
        	for(int j = 1; j < i - 1; j++) {
        		dp[i] = max(dp[i], j * (i - j), j * dp[i - j]);
        	}
        }
        
    	return dp[n];
    }
    
    private int max(int a, int b, int c) {
    	return Math.max(a, Math.max(b, c));
    }
    
    public int integerBreak2(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
    
}
